package cn.cxq.learning.dynamic_programming;

import java.util.Arrays;

/**
 * 牛客题霸-算法篇
 * 换钱的最少货币数
 * 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M 热度指数：8500
 * 本题知识点： 动态规划
 *  算法知识视频讲解
 * 题目描述
 * 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
 * 如果无解，请返回-1.
 * 【要求】
 * 时间复杂度O(n \times aim)O(n×aim)，空间复杂度On。
 * 示例1
 * 输入
 * 复制
 * [5,2,3],20
 * 返回值
 * 复制
 * 4
 * 示例2
 * 输入
 * 复制
 * [5,2,3],0
 * 返回值
 * 复制
 * 0
 * 示例3
 * 输入
 * 复制
 * [3,5],2
 * 返回值
 * 复制
 * -1
 * 备注:
 * 0 \leq n \leq 1\,0000≤n≤1000
 * 0 \leq aim \leq 5\,0000≤aim≤5000
 *  关联企业
 * 快手腾讯字节跳动滴滴
 *  关联职位
 * 研发前端
 */
public class MinMoney {

    public int minMoney (int[] arr, int aim) {

        int[] dp = new int[aim + 1];

        Arrays.fill(dp, aim + 1);

        dp[0] = 0;

        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                if (j >= arr[i]) {
                    dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
                }
            }
        }

        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
}
